#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10 // 哈希表大小

// 哈希表结点结构
struct HashNode
{
    int key;               // 键
    int value;             // 值
    struct HashNode *next; // 下一个结点指针（用于链地址法）
};

// 哈希表结构
struct HashTable
{
    struct HashNode **buckets; // 桶数组（每个桶是一个链表）
    int size;                  // 表大小
};

// 创建新结点
struct HashNode *createNode(int key, int value)
{
    struct HashNode *node = (struct HashNode *)malloc(sizeof(struct HashNode));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

// 创建哈希表
struct HashTable *createHashTable(int size)
{
    struct HashTable *table = (struct HashTable *)malloc(sizeof(struct HashTable));
    table->size = size;
    table->buckets = (struct HashNode **)malloc(size * sizeof(struct HashNode *));

    // 初始化所有桶为空
    for (int i = 0; i < size; i++)
    {
        table->buckets[i] = NULL;
    }

    return table;
}

// 除留余数法哈希函数（展示冲突）
int hashFunction(int key)
{
    return key % TABLE_SIZE;
}

// 向哈希表插入键值对（使用链地址法处理冲突）
void insert(struct HashTable *table, int key, int value)
{
    // 计算哈希值
    int index = hashFunction(key);

    // 创建新结点
    struct HashNode *newNode = createNode(key, value);

    // 如果桶为空，直接插入
    if (table->buckets[index] == NULL)
    {
        table->buckets[index] = newNode;
    }
    else
    {
        // 使用头插法（简单高效）
        newNode->next = table->buckets[index];
        table->buckets[index] = newNode;

        // 打印冲突信息
        printf("Collision detected! Key %d collides with key %d at index %d\n",
               key, table->buckets[index]->next->key, index);
    }
}

// 打印哈希表（展示链地址法）
void printHashTable(struct HashTable *table)
{
    printf("\nHash Table with Chain Addressing:\n");
    printf("Index\tKeys (Key:Value)\n");
    printf("------------------------\n");

    for (int i = 0; i < table->size; i++)
    {
        printf("%d\t", i);
        struct HashNode *current = table->buckets[i];

        if (current == NULL)
        {
            printf("NULL");
        }
        else
        {
            while (current != NULL)
            {
                printf("%d:%d", current->key, current->value);
                if (current->next != NULL)
                {
                    printf(" -> ");
                }
                current = current->next;
            }
        }
        printf("\n");
    }
}

// 主函数测试（展示冲突处理）
int main()
{
    // 创建哈希表
    struct HashTable *table = createHashTable(TABLE_SIZE);

    printf("Demonstrating hash collisions with chain addressing:\n");

    // 插入键值对（故意制造冲突）
    insert(table, 10, 100); // 索引0
    insert(table, 20, 200); // 索引0 (冲突)
    insert(table, 30, 300); // 索引0 (冲突)

    insert(table, 15, 150); // 索引5
    insert(table, 25, 250); // 索引5 (冲突)
    insert(table, 35, 350); // 索引5 (冲突)

    insert(table, 12, 120); // 索引2
    insert(table, 22, 220); // 索引2 (冲突)

    // 打印哈希表
    printHashTable(table);

    return 0;
}